package second.mstack;

import java.util.Arrays;
import java.util.LinkedList;

public class Solution04 {
    public int trap(int[] height) {
        int[] maxLeft = new int[height.length];
        int[] maxRight = new int[height.length];
        maxLeft[0] = height[0];
        for (int i = 1; i < maxLeft.length; i++) {
            maxLeft[i] = Math.max(maxLeft[i - 1], height[i]);
        }
        maxRight[height.length - 1] = height[height.length - 1];
        for (int i = height.length - 2; i >= 0; i--) {
            maxRight[i] = Math.max(maxRight[i + 1], height[i]);
        }
        int sum = 0;
        for (int i = 1; i < height.length - 1; i++) {
            int left = maxLeft[i];
            int right = maxRight[i];
            int h = Math.min(left, right);
            h -= height[i];
            sum += h;
        }
        return sum;
    }
}
